package com.zyk.leetcode;

import java.util.Arrays;

/**
 * @author zhangsan
 * @date 2021/4/25 22:28
 */
public class C16 {

    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int ans = twoSum(nums, 0, nums.length - 1, target);
        if (ans == target) return target;
        for (int i = 1; i < nums.length - 2; i++) {
            if (nums[i] == nums[i - 1]) continue;
            int p = twoSum(nums, i, nums.length - 1, target);
            if (p == target) return target;
            if (Math.abs(target - p) < Math.abs(target - ans)) {
                ans = p;
            }
        }
        return ans;
    }

    public int twoSum(int[] nums, int start, int r, int target) {
        int l = start + 1;
        int ans = 0;
        int abs = Integer.MAX_VALUE;
        while (l < r) {
            int v = nums[l] + nums[r] + nums[start];
            if (v == target) {
                return target;
            } else if (v < target) {
                if (target - v < abs) {
                    abs = target - v;
                    ans = nums[start] + nums[l] + nums[r];
                }
                l++;
                while (l < nums.length && nums[l] == nums[l - 1]) l++;
            } else {
                if (v - target < abs) {
                    abs = target - v;
                    ans = nums[start] + nums[l] + nums[r];
                }
                r--;
                while (r >= 0 && nums[r] == nums[r + 1]) r--;
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        C16 test = new C16();
        int[] nums = {-1,2,1,-4};
        int target = 1;
        System.out.println(test.threeSumClosest(nums, target));
    }

}
